package cn.edu.xjtu.剑指offer.reversePrint;

import cn.edu.xjtu.Util.ListNode.ListNode;
import cn.edu.xjtu.Util.ListNode.ListNodeUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 剑指 Offer 06. 从尾到头打印链表
 * <p>
 * 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
 */
public class Solution {
    public static void main(String[] args) {
        Solution solu = new Solution();
        ListNode head = ListNodeUtil.generate(new int[]{1, 3, 2});
        System.out.println(Arrays.toString(solu.reversePrint(head)));
    }

    /**
     * 存下每一个元素，然后在数组中反向打印
     *
     * @param head
     * @return
     */
    public int[] reversePrint1(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        int[] ret = new int[list.size()];
        for (int i = ret.length - 1; i >= 0; i--) {
            ret[ret.length - i - 1] = list.get(i);
            System.out.println(ret[i]);
        }
        return ret;
    }

    /**
     * 递归打印
     *
     * @param head
     * @return
     */
    public int[] reversePrint(ListNode head) {
        ArrayList<Integer> list = new ArrayList<>();
        help(head, list);
        int[] ret = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ret[i] = list.get(i);
        }
        return ret;
    }

    private void help(ListNode head, ArrayList<Integer> list) {
        if (head == null) {
            return;
        }
        help(head.next, list);
        list.add(head.val);
    }
}
